package com.leet.backtracking;

import java.util.ArrayList;
import java.util.List;

public class Zushuzonghe1 {
    int sumTemp(List<Integer> tmp){
        int sum = 0;
        for(Integer item:tmp){
            sum += item;
        }
        return sum;

    }
    void backtracking(int[] candidates, int target, List<Integer> tmp,List<List<Integer>> ans,int index){
        if(sumTemp(tmp) >= target){
            if(sumTemp(tmp)==target){
                ans.add(new ArrayList<>(tmp));
            }
            return;
        }
        for(int i = index;i < candidates.length;i++){
            tmp.add(candidates[i]);
            backtracking(candidates, target, tmp, ans,i+1);
            tmp.remove(tmp.size()-1);
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> tmp = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        backtracking(candidates, target, tmp, ans,0);
        return ans;
    }
}
